//https://leetcode.cn/problems/perfect-squares/?envType=study-plan-v2&envId=top-100-liked
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <climits>

using namespace std;

//https://github.com/fuxuemingzhu/Leetcode-Solution-All/blob/main/200-299/279.%20Perfect%20Squares%20%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.md
//完全平方数.cpp -279
//判断一个正整数最少能成为几个数字的平方和。

class Solution {
public:
    int numSquares(int n) {
        // dp[i] means how many perfect squres it needs.
        vector<int> dp;
        dp.push_back(0);
        for (int i = 1; i <= n; ++i) {
            int val = INT_MAX;
            for (int j = 1; j * j <= i; ++j) {
                val = min(val, dp[i - j * j] + 1);
            }
            dp.push_back(val);
        }
        return dp[n];
    }
};